Telecommunications are fundamental to the operation of modern society. The performance and cost advantages of modern telecommunications have lead to the widespread use of computer networks to transmit voice, image, and data around the world. Those computer networks enable billions of people to easily, quickly, and at low cost communicate with one another, share information, and transfer data.
Computer networks are based on an agreed set of protocols that enable messages to be transmitted from a source, passed along the telecommunication network, and received at a destination. Messages have at least two parts, the actual information that the sender wants to transfer to the destination and the routing information that controls who receives the message. The agreed upon protocols enable a sender to obtain the address of the destination and the various “stations” of the network to handle the message as it passes through the network to the destination.
A computer network is a collection of nodes (terminals or stations) that are interconnected by links (a connection between two nodes). Each node has a unique network address. Some nodes are directly connected to one another (neighbors) while others are connected through intermediate nodes. The nodes use the message routing information to route the source's message through the links and nodes from the sender node to the destination node. Each transfer of the message from one node to another is a hop.
As used herein a ‘network’ is an interactive system of computers that often includes peripherals, terminals, and databases that are connected by communications lines. Such communication lines may be wired, fiber optic, wireless, microwave, line of sight, repeaters or other communication paths. The term ‘node’ is used herein expansively. A node is a communication connection point, a communication end point, or a communication distribution point. It is an active entity capable of sending, receiving, or forwarding information over a communications channel. A physical node may be a computer, a terminal or a peripheral. A virtual node may exist as a code construct. While different networks may use different types of nodes the term node should be understood as any entity that receives and transmits messages. By ‘dynamic’ it is meant an interactive network or process is characterized by change and adaptation. A dynamic network adapts to changes and to inputs to and from itself as required to complete its tasks. For example, a new node may join a dynamic network. Required processes such as node addresses are kept and distributed as needed. Nodes can leave, and other networks may be merged. All the while the network still services its clients.
A small ‘fixed’ computer network with stable members can relatively easily determine the correct or best path for passing messages between any two nodes. But as the network gets larger the number of ‘correct’ paths from one node to the others gets very large. There are numerous methods of selecting ‘correct’ paths. However, no matter the method it is beneficial to reduce the routing information signal handling requirements.
Greatly complicating the difficultly of choosing a correct path to transfer messages between a source node and a destination node are wireless ad hoc networks. A wireless ad hoc network is a wireless network that sets itself up external of a pre-existing infrastructure. Wireless ad hoc networks are decentralized in the sense that no controlling node manages the entire network. Each wireless ad hoc network node participates in routing by forwarding messages for other nodes dynamically based on network connectivity.
An ad hoc network should be understood broadly as an improvised, possibly impromptu, dynamically formed network. An ad hoc network forms as needed to service its clients. Then it grows, shrinks, moves, and dissipates as needed.
Traditional routing protocols for computer networks and wireless ad hoc networks in particular rely on network-wide dissemination of signaling packets that provide proactive updates to the state of links (which nodes are connected by links or the distances to destinations), or on-demand requests for routes to destinations. However, as the number of nodes, dynamic connectivity changes, and new traffic flows increase both approaches tend to incur excessive signaling overhead.
Making the problem of determining message paths even more difficult are mobile ad hoc networks (MANET). In a MANET a particular node may change its physical location, which changes the nearest nodes it can directly connect to, which changes “best” message paths, which makes keeping track of good message paths even more difficult. The signaling overhead required to track all nodes in a network and to determine how to pass messages from any particular source node to any particular destination node can be prohibitive.
In a prior art computer network a particular node might be a server having services to offer, a client in need of services, or a router for passing information. To properly use a service a node must be made aware of the availability of that service. For example, to send a message a sender node must be able to find the address of a destination node and a message path. The sender node must use a service that can supply that information, and for that the sender must know how to contact the service. Publishing that information requires service discovery. Considerable work has been performed regarding implementing service discovery in computer networks. Typically service-discovery is performed by operating on top of a routing infrastructure or as an augment of an existing routing protocol.
Interestingly, prior solutions for making routing more scalable do not integrate destination-based routing with an adaptive publish-subscribe mechanism in a way that reduces the signaling required for both routing and service discovery.
Prior routing protocols in computer networks and MANETs assumed that the mappings of destination names to either addresses or routes were independent of actual routing. Various routing approaches were used, including hierarchical, limiting the dissemination of control messages, distributed hash tables (DHT), Bloom filters, virtual or geographical coordinates, or sets of dominating nodes to reduce the size of routing tables or the amount of route signaling.
Hierarchical routing schemes organize nodes into clusters. Some hierarchical routing schemes reduce signaling overhead by limiting the propagation of control messages based on their distance from an originating node. One problem with hierarchical routing schemes in a MANET is that the affiliation of nodes to specific clusters is easily broken when a node moves. Re-establishing affiliations incurs considerable signaling overhead. Unless re-established, incorrect routing can result in signaling decays based on distances to specific links
Distributed hash tables (DHT)-based schemes are attractive because a distributed hash table grows only logarithmically as the number of destinations grows. However, typical distributed hash table schemes define a virtual topology, which requires substantial signaling overhead to maintain the various links of virtual topologies that are defined in large MANET networks.
Automatic Incremental Routing (AIR) avoids virtual topologies by using variable-length prefix labels instead of addresses. Another approach is using hashing node identifiers of destinations in Bloom filters, which are then used in routing updates. Unfortunately, such schemes suffer from “false positives” that incur considerable signaling overhead.
Other routing schemes for MANET rely on geographical coordinates for routing. Unfortunately such protocols require ubiquitous GPS services yet still incur routing signal overhead when discovering the geo-locations of destinations node. Some other routing schemes use virtual coordinates consisting of the distances between nodes and reference nodes. The main limitation of this type of routing scheme is that the virtual coordinates of multiple nodes may be assigned the same virtual coordinates. This is because there is simply no inherent uniqueness to a specific vector of distances to beacons. The result is either possible incorrect routing or the use of additional signaling (typically flooding) to resolve false positives.
There are also many proposals in the prior art to reduce the number of relays needed to forward signaling messages for a given number of destinations. The best known example uses multipoint relays, for example, P. Jacquet, P. Muhlethaler, T. Clausen, A. Laouiti, A. Qayyum, and L. Viennot, “Optimized Link State Routing Protocol for Ad Hoc Networks,” IEEE INMIC 2001, pages 62-68, 2001. However, such proposals require the establishment and maintenance of “connected dominating sets,” i.e., the nodes selected to forward signaling messages must form a connected sub-graph. This usually requires a large subset of nodes, especially in dynamic topologies.
There has also been work performed on resource and service discovery in ad hoc networks. Interestingly, such work either assumes that names are mapped to addresses and that routing to those addresses is independent of or augmented by existing routing protocols of service discovery functionality.
In addition to the classic routing schemes discussed above, ad hoc networks can also simply use flooding for forwarding data. A sender sends a message to its neighbors, which then pass that message on to its other neighbors, and so on. This approach involves very large signaling overhead, especially as the wireless ad hoc network grows.
In view of the foregoing a new approach to routing in computer networks based on publish-subscribe mechanisms would be beneficial. Even more beneficial would be an adaptive protocol for routing in wireless ad hoc networks. In particular, an adaptive protocol that uses distance vectors for routing in computer networks and that integrates a sub-set of nodes to serve as controllers that maintain routes to nearby destination nodes, maintains routes to all known controllers using distance vectors, and uses publish-subscribe mechanisms in which destinations inform controllers of routes to them and in which sources obtain routes to destinations would be useful.